package algorithm.middle;

public class MaxChunksToSorted769 {


    /**
     * 给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
     * <p>
     * 我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
     * <p>
     * 返回数组能分成的最多块数量。
     * <p>
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: arr = [4,3,2,1,0]
     * 输出: 1
     * 解释: 2 3 4 5 6 1
     * 将数组分成2块或者更多块，都无法得到所需的结果。
     * 例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
     * 1 0 2 4 3
     *
     * @param arr
     * @return
     */
    public static int maxChunksToSorted(int[] arr) {
        int count = 0;
        int max = -1;
        //每次取当前期望最小值的左边为一次切分。切完之后最小的之为左边这组最大值+1，继续往后切分。
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            //[1,4,3,6,0,7,8,2,5] 确保每次左边该组的最大值不要超过i坐标的排序。不然是无法达成左边为依次最小升序的。
            if ( max <= i ) {
                count++;
                max = -1;
                //最后一位数字符合条件参与了计算，直接返回。
                if (i==arr.length-1){
                    return count;
                }
            }
        }
        //最后一位数组没参与分组计算，手动增加一个组。
        return count + 1;
    }

    public static void main(String[] args) {
        /*
         1 0
         2
         5 3 4
         */
        maxChunksToSorted(new int[]{2,0,1,3});
    }


    /**
     * 首先找到从左块开始最小块的大小。如果前 k 个元素为 [0, 1, ..., k-1]，可以直接把他们分为一个块。当我们需要检查 [0, 1, ..., n-1] 中前 k+1 个元素是不是 [0, 1, ..., k] 的时候，只需要检查其中最大的数是不是 k 就可以了
     *
     * 作者：LeetCode
     * 链接：https://leetcode.cn/problems/max-chunks-to-make-sorted/solution/zui-duo-neng-wan-cheng-pai-xu-de-kuai-i-by-leetcod/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param arr
     * @return
     */
    public int maxChunksToSorted2(int[] arr) {
        int ans = 0, max = 0;
        for (int i = 0; i < arr.length; ++i) {
            max = Math.max(max, arr[i]);
            if (max == i) ans++;
        }
        return ans;
    }

}
